package main

import "fmt"

const Int_MAX = int(^uint(0) >> 1) //位操作

type Nd struct {
	value int
	next  int
}

var NL []Nd

func main() {
	arr := []int{1, 9, 2, 8, 3, 7, 6, 4, 5, 10}
	InitList(arr) //初始化
	ListSort()    //排序
	Arrange()     //综合处理
}

func InitList(arr []int) {
	var nd Nd
	nd = Nd{Int_MAX, 1}
	NL = append(NL, nd) //插入第一个节点，第一个节点最大，编号1

	for i := 0; i < len(arr); i++ {
		nd = Nd{arr[i], 0}
		NL = append(NL, nd)
	}

	fmt.Println(NL)
}

// 列表排序
func ListSort() {
	var i, low, high int

	for i = 2; i < len(NL); i++ {
		low = 0
		high = NL[0].next

		for NL[high].value < NL[i].value {
			low = high
			high = NL[high].next
		}

		NL[low].next = i
		NL[i].next = high

		fmt.Println(NL)
	}
}

//地址排序，插入排序
func Arrange() {
	p := NL[0].next
	for i := 1; i < len(NL); i++ {
		for p < i { //i之前都是排序q:=好的
			p = NL[p].next
		}
		q := NL[p].next //下一个要排序的记录
		if p != i {
			NL[p].value, NL[i].value = NL[i].value, NL[p].value //数据交换
			NL[p].next = NL[i].next                             //修改next
			NL[i].next = p                                      //地址插入

		}
		p = q //循环下一个

	}
	for i := 1; i < len(NL); i++ {
		fmt.Println(NL[i].value)
	}
}
